import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:38917
 * Date:2025/4/22
 * Time:18:27
 */
class ListNode {
    //
    public static class Node {
        protected final int val;
        protected Node next;
        protected Node(int val) {
            this.val = val;
        }
    }
    //
    public Node createList1() {
        Node node1 = new Node(1);
        Node node2 = new Node(1);
        Node node3 = new Node(1);
        Node node4 = new Node(1);
        Node node5 = new Node(1);
        Node node6 = new Node(1);
        Node node7 = new Node(1);
        Node node8 = new Node(1);
        Node node9 = new Node(1);
        Node node10 = new Node(1);
        Node node11 = new Node(1);
        Node node12 = new Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        node9.next = node10;
        node10.next = node11;
        node11.next = node12;
        return node1;
    }
    //
    public Node createList2() {
        Node node1 = new Node(9);
        Node node2 = new Node(1);
        Node node3 = new Node(1);
        Node node4 = new Node(1);
        Node node5 = new Node(1);
        Node node6 = new Node(1);
        Node node7 = new Node(1);
        Node node8 = new Node(1);
        Node node9 = new Node(1);
        Node node10 = new Node(1);
        Node node11 = new Node(1);
        Node node12 = new Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        node9.next = node10;
        node10.next = node11;
        node11.next = node12;
        return node1;
    }
}

public class Solution {
    private static final ListNode.Node head1 = new ListNode().createList1();
    private static final ListNode.Node head2 = new ListNode().createList2();
    /*public static ListNode.Node addTwoNumbers(ListNode.Node head1, ListNode.Node head2) {
        long count1 = 1, count2 = 1;//记录位数
        long sum1 = 0, sum2 = 0;//记录总和
        while (head1 != null){
            sum1 += (long) head1.val * count1;
            count1 *= 10;
            head1 = head1.next;
        }
        while (head2 != null){
            sum2 += (long) head2.val * count2;
            count2 *= 10;
            head2 = head2.next;
        }
        if (sum1 == 0 && sum2 == 0){
            return new ListNode.Node(0);
        }
        long sum = sum1 + sum2;
        ArrayList<ListNode.Node> ret = new ArrayList<>();
        while (sum != 0) {
            ListNode.Node temp = new ListNode.Node((int) (sum % 10));
            ret.add(temp);
            sum = sum / 10;
        }
        for (int i = 0; i < ret.size() - 1; i++) {
            ret.get(i).next = ret.get(i + 1);
        }
        return ret.get(0);
    }*/
    public static ListNode.Node addTwoNumbers(ListNode.Node head1, ListNode.Node head2) {
        // 构造哑巴节点 newHead，最后返回 newHead.next, 以方便处理新链表的头节点。
        ListNode.Node newHead = new ListNode.Node(0);
        ListNode.Node cur = newHead; // cur 一直会变化（前进）
        int carrier = 0; // 进位

        // 只要有没走到头的链表或者进位不为 0 就一直前进。
        while (head1 != null || head2 != null || carrier != 0) {
            // 求和，考虑可能有链表走到头
            int sum = (head1 != null ? head1.val : 0) + (head2 != null ? head2.val : 0) + carrier;

            // 在尾部添加节点
            cur.next = new ListNode.Node(sum % 10);
            cur = cur.next;

            // 更新进位，并向两个链表尾部前进
            carrier = sum / 10;
            if (head1 != null) head1 = head1.next;
            if (head2 != null) head2 = head2.next;
        }

        return newHead.next;
    }
    public static void main(String[] args) {
        ListNode.Node ret = addTwoNumbers(head1, head2);
        while (ret != null) {
            System.out.print(ret.val + " ");
            ret = ret.next;
        }
    }
}
